package com.sheng.leetcode.year2022.swordfingeroffer.day22;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/09/20
 *<p>
 * 剑指 Offer 56 - II. 数组中数字出现的次数 II<p>
 *<p>
 * 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。<p>
 *<p>
 * 示例 1：<p>
 * 输入：nums = [3,4,3,3]<p>
 * 输出：4<p>
 *<p>
 * 示例 2：<p>
 * 输入：nums = [9,1,7,9,7,9,7]<p>
 * 输出：1<p>
 *<p>
 * 限制：<p>
 *<p>
 * 1 <= nums.length <= 10000<p>
 * 1 <= nums[i] < 2^31<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword0056Two {

    @Test
    public void test01() {
//        int[] nums = {3,4,3,3};
        int[] nums = {9,1,7,9,7,9,7};
        System.out.println(new Solution56Two().singleNumber(nums));
    }
}
class Solution56Two {
    public int singleNumber(int[] nums) {
        // 创建一个长度为32的数组
        int[] ints = new int[32];
        // 记录所有数字的各二进制位的1的出现次数
        for (int num : nums) {
            for (int i = 0; i < 32; i++) {
                ints[i] += num & 1;
                // 无符号右移，例-5 >>> 1 = 2147483645
                // 原码：10000000 00000000 00000000 00000101
                // 反码：11111111 11111111 11111111 11111010
                // 补码：11111111 11111111 11111111 11111011
                // 无符号右移后的补码：01111111 11111111 11111111 11111101
                // 即 2147483645
                num >>>= 1;
            }
        }
        int ans = 0;
        for (int i = 31; i >= 0; i--) {
            // 从高位往低位计算
            // ans *= 2
            ans <<= 1;
            // 恢复第i位的值
            ans ^= ints[i] % 3;
        }
        return ans;
    }
}
